// 15.1.2　记忆化搜索
// function fib(n){
//     if(n == 1 || n == 2){
//       return 1;
//     }
//     return fib(n - 1) + fib(n-2);
//   }
//   console.log(fib(10)); // 144
// function fib(n) {
//     if(n == 1 || n === 2){
//        return 1;
//     }
//     var a = 1, b = 1;
//     for (var i = 3; i <= n; i++) {
//       const c = a + b;
//       a = b;
//       b = c;
//     }
//     return b;
// }
// function fib1(n) {
//     var table = [0, 1, 1]; // 表
//     for (var i = 3; i <= n; i++) {
//       table[i] = table[i - 1] + table[i - 2];// 填表
//     }
//     return table[n];
// }
// function fib3(n) {
//     if (fib.cache[n]) {
//       return fib.cache[n];
//     }
//     return fib.cache[n] = fib(n - 1) + fib(n - 2);
//   }
// fib.cache = {
// 1: 1,
// 2: 1
// }
// console.log(fib3(10)); // 354224848179262000000
// console.log(fib(10), fib1(10))

// 15.2　找零钱
// function coinChange(coins, amount) {// 总额，面额数组
//     var ans = Infinity;
//     if (amount === 0) { // 分支1
//       return 0;
//     } else {  // 分支2
//       for (let coin of coins) {
//         console.log("test");
//         if (coin <= amount) {
//           count = coinChange(coins, amount - coin);
//           if (count !== -1) {
//             ans = Math.min(ans, count + 1);
//           }
//         }
//       }
//     }
//     return ans == Infinity ? -1 : ans;
//   }
//   console.log(coinChange([1, 2, 5], 11)); // 3
// function coinChange(coins, n) {
//     let cache = coinChange.cache;
//     if (cache[n] != void 0) {
//       return cache[n];
//     }
//     let ans = Infinity;
//     for (let coin of coins) {
//       if (n >= coin) {
//         console.log('TEST'); // 28
//         let ret = coinChange(coins, n - coin);
//         if (ret !== -1) {
//           ans = Math.min(ans, ret + 1);
//         }
//       }
//     }
//     return cache[n] = (ans == Infinity ? -1 : ans);
//   }
//   coinChange.cache = { 0: 0 };
//   console.log(coinChange([1, 2, 5], 11));
// function coinChange(coins, n) {
//     var table = [0]// table变量通常也写成dp
//     for (var j = 1; j <= n; j++) {
//       table[j] = Infinity;
//       for (var i = 0; i < coins.length; i++) {
//         var coin = coins[i];
//         if (j < coin) continue;
//           table[j] = Math.min(table[j], table[j - coin] + 1); 
//       }
//     }
//     return table[n] == Infinity ? -1 : table[n];
//   }
// console.log(coinChange([1, 2, 7, 8, 12, 50], 15));
// console.log(coinChange([1, 2, 5], 11));




// 15.3　最长不下降子序列
// function longestNonDecreasingSequence(array){
//     var dp =  [1]  ;
//     var max = 1, k = 0;
//     for (var i = 1; i < array.length; i++) {
//       dp[i] = 1;
//       for (var j = 0; j < i; j++) {
//         if (array[i] >= array[j]){// 不下降，就是等于或大于
//           if(dp[i] < dp[j] + 1 ){
//             dp[i] = dp[j] + 1;
//           }  
//         } 
//       }
//       if(dp[i] > max){
//         max = dp[i];
//         k = i; // 最大索引
//       }
//     }
//     var ret = [ array[k] ];
//     var m = max; 
//     var i = k-1;	// 从最后一个位置往前找
//     while( m > 1) {
//       // 相邻的dp[i]都是相等或相差1
//       if(dp[i] == m - 1 && array[i] <= array[k]){
//         ret.unshift(array[i]);
//         k = i;
//         m--;
//       }
//       i--;
//     }
//     return ret;// [1,2,3,3,9,11]
//   }
// console.log(longestNonDecreasingSequence([1,2,3,-9,3,9,0,11])); 

// 15.4　最长公共子序列
// function longestCommonSequence(a, b){
//     var an = a.length, bn = b.length;
//     var dp = [];
//     dp[-1] =  new Array(bn).fill(0);
//     dp[-1][-1] = 0;
//     for (var i = 0; i < an; i++) {
//       dp[i] = [];
//       dp[i][-1] = 0;
//       for(var j = 0; j < bn; j ++){
//         if(a[i] === b[j]){
//           dp[i][j] = dp[i-1][j-1]+1;
//         }else{
//           dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
//         }
//       }
//     }
//     var i = an - 1, j = bn-1, lcs = '';
//     while(i >= 0 && j>=0) {
//       if(a[i] == b[j]){
//         lcs = a[i] + lcs;// 从a字符串的后面起，收集两个字符串都有的字符
//         i--;
//         j--;
//       } else if(dp[i-1][j] < dp[i][j-1]){// 上面少于左边
//         j--;
//       } else if(dp[i][j-1] <= dp[i-1][j]){
//         i--;
//       }
//     }
//     console.log(dp[an-1][bn-1], lcs);
//     return lcs;
//   }
//   longestCommonSequence("ABCPDSFJGODIHJOFDIUSHGD",
//     "OSDIHGKODGHBLKSJBHKAGHI");  // 9 "SDIHODSHG"
// 15.5　爬楼梯
// function climbStairs(i){
//     var dp = [0, 1, 2];
//     if(i < 3){
//       return dp[i];
//     }
//     for(var j = 3; j <= i; j++){
//       dp[j] = dp[j-1]+ dp[j-2];
//     }
//     return dp[i];
// }
// console.log(3)

// 15、背包问题 
// function backpack(w, v, n, cap) {
//     if (n == 0 || w.length == 0 || v.length == 0 || cap == 0) {
//       return 0;
//     }
  
//     // 创建一个n * (cap+1)的矩阵
//     var dp = [];
//     for (let i = 0; i < n; i++) {
//       dp[i] = new Array(cap + 1).fill(0);
//     }
  
//     // 初始化第0行
//     for (let i = 0; i < cap + 1; i++) {
//       dp[0][i] = i >= w[0] ? v[0] : 0;
//     }
  
//     // 初始化第0列
//     for (let i = 0; i < n; i++) {
//       dp[i][0] = 0;
//     }
//     for (let i = 1; i < n; i++) {
//       for (let j = 1; j < cap + 1; j++) {
//         if (j >= w[i]) {
//           dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
//         } else {
//           dp[i][j] = dp[i - 1][j];
//         }
//       }
//     }
//     console.log("[" + dp.map(function (el) {
//       return JSON.stringify(el) + "\n"
//     }) + "]");
//     return dp[n - 1][cap];
//   }
  
//   var res = backpack([1, 2, 3], [6, 10, 12], 3, 5);
//   console.log(res);

